package com.leetcode.weekly.contest.no283th;

import com.leetcode.common.model.TreeNode;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2022-03-06 11:07
 */
public class A03_根据描述创建二叉树 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][] descriptions = {{85,82,1},{74,85,1},{39,70,0},{82,38,1},{74,39,0},{39,13,1}}
        
        
        ;
    TreeNode treeNode = solution.createBinaryTree(descriptions);

    System.out.println(treeNode);
  }


  static
  class Solution {
    public TreeNode createBinaryTree(int[][] descriptions) {

      Map<Integer, TreeNode> map = new HashMap<>();
      Set<Integer> childValues = new HashSet<>();
      Set<Integer> parentValues = new HashSet<>();

      for (int[] description : descriptions) {
        int parent = description[0];
        int child = description[1];
        int isLeft = description[2];

        parentValues.add(parent);
        childValues.add(child);

        TreeNode parentNode = map.get(parent);
        if (parentNode == null) {
          parentNode = new TreeNode(parent);
          map.put(parent, parentNode);
        }

        TreeNode childNode = map.get(child);
        if (childNode == null) {
          childNode = new TreeNode(child);
          map.put(child, childNode);
        }

        if (isLeft == 1) {
          parentNode.left = childNode;
        } else {
          parentNode.right = childNode;
        }
      }

      for (Integer value : parentValues) {
        if (!childValues.contains(value)) {
          return map.get(value);
        }
      }
      return null;
    }
  }

}
